#include <stdio.h>
#include <stdlib.h>
#include "single_linked_list.cpp"
// 采用带头结点的单链表保存单词
// 当两个单词有相同的后缀时
// 可共享后缀存储空间
// 例如 loading 和 being
// 找出两个链表共同后缀的起始位置

// 尾部对其后 同步遍历
// 求链表长度算法
int GetListLen(LinkedList L) {
	LNode *ptr = L;
	int len = 0;
	while(ptr) {
		ptr = ptr->next;
		len++;
	}
	return len;
}
LNode *GetCommonNodeStart(LinkedList &S1, LinkedList &S2) {
	int len1 = GetListLen(S1), len2 = GetListLen(S2);
	LNode *ptr1 = S1, *ptr2 = S2;
	// 尾部对其
	for(; len1 > len2; len2++)
		ptr1 = ptr1->next;
	for(; len2 > len1; len1++)
		ptr2 = ptr2->next;
	// 同步遍历
	while(ptr1 != ptr2 && ptr1) {
	 	ptr1 = ptr1->next;
	 	ptr2 = ptr2->next;
	}
	return ptr1;
}

int main() {    
	LinkedList L1;
    InitList(L1);

    // 插入
    ListAppend(L1, 2);
    ListAppend(L1, 5);
    ListAppend(L1, 9);
    ListAppend(L1, 7);
    ListAppend(L1, 3);
    ListAppend(L1, 6);
    PrintList(L1);

	LinkedList L2;
    InitList(L2);

    // 插入
    ListAppend(L2, 1);
    ListAppend(L2, 2);
    ListAppend(L2, 3);
	GetElem(L2,3)->next = GetElem(L1,3);
	PrintList(L2);

	LNode *r = GetCommonNodeStart(L1,L2);
	if (r != NULL)
		printf("===> %d\n",r->data);
	else
		printf("没有公共部分");
	return 0;
}
